"""


n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
第一个整数是 0
一个整数在序列中出现 不超过一次
每对 相邻 整数的二进制表示 恰好一位不同 ，且
第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

 

示例 1：

输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同
示例 2：

输入：n = 1
输出：[0,1]
 

提示：

1 <= n <= 16

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/gray-code
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
"""
from typing import List

"""
不管n为几，当前n的格雷码中的前一半始终为n - 1的全部，所以这时我们可以忽略n在格雷码中的影响

这时我们将格雷码编号：

[000, 001, 011, 010, 110, 111, 101, 100 ...]
  0,   1,   2,   3 ,   4,   5,  6,   7,  ...
这里的0 ~ 7... 转换为二进制后我们成为二进制码，比如我们要求解5对应的格雷码，这里5对应的二进制码就是0101（5的二进制）
二进制码对应的每一位就是小b，，格雷码每一位是g，这里讲解过程中在前面补0方便理解，这里的 \/ 就是异或的运算
0   0   1   0   1
0   b3  b2  b1  b0
  \/  \/  \/  \/ 
  g3  g2  g1  g0
   0   1   1   1
所以我们由5（0101）推出对应的格雷码为0111
这里解释一下(i >> 1) ^ i，i>>1其实将i每一位向后移动一位，这时和i取异或，相当于和自己的后一位取余
b3 b2  b1  b0  (i)
0  b3  b2  b1  (i >> 1)
g3 g2  g1  g0  (结果) 
当 n=3 list有8个元素
0 1 2 3 4 5 6 7
其每个都有对应的的格雷码 如5 对应的格雷码是0111——>换算成二进制是7但是这并无实际意义 7只是5对应的格雷码按照2->10进制转化出来的方便记录
"""
class SolutionOne:
    def grayCode(self, n: int) -> List[int]:
        return [i >> 1 ^ i for i in range(1 << n)]

"""
会了不难 难了不会 与其说是算法题更像是某领域的常识 找到规律套公式结果就出来了
即：下一个数组的后一半：对称反转+2的n-1次方
[0, 1]
[0, 1, 3, 2]   3-1 = 2-0 =2 =2**1
[0, 1, 3, 2, 6, 7, 5, 4]  6-2 = 7-3 = 5-1 = 4-0 = 4 = 2**2
[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8]
[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8, 24, 25, 27, 26, 30, 31, 29, 28, 20, 21, 23, 22, 18, 19, 17, 16]
[0, 1, 3, 2, 6, 7, 5, 4, 12, 13, 15, 14, 10, 11, 9, 8, 24, 25, 27, 26, 30, 31, 29, 28, 20, 21, 23, 22, 18, 19, 17, 16, 48, 49, 51, 50, 54, 55, 53, 52, 60, 61, 63, 62, 58, 59, 57, 56, 40, 41, 43, 42, 46, 47, 45, 44, 36, 37, 39, 38, 34, 35, 33, 32]

"""
class SolutionTwo:
    def grayCode(self, n: int):
        list=[0,1]
        if n==1:
            return list
        for i in range(2,n+1):
            for j in range(int(len(list)-1), -1, -1):
                list.append(list[j]+2**(i-1))
        return list
"""
每个数字 都有左右两个“邻居“  找到每个数字左右两个邻居 但符合要求的邻居并不唯一 
每个人的右手拉别人的左手形成一个闭环求解
但本题不需要这么麻烦 且算法并未实现 或许这条思路有问题 
"""
class SolutionThree(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        list=[]
        i=1
        while i<2**n-1:
            list.append(i)
            i=i*2

        #print(list)
        def  isNeighbour(a,b):
            a=int(a)
            b=int(b)
            if a^b in list:
                return True
            else:
                return False
        listFrom=[]
        listTo=[0]
        for i in range(1, 2**n):
            listFrom.append(i)
        #print(listFrom)
        while len(listFrom) != 0:
            for item in listFrom:
                if isNeighbour(item, listTo[len(listTo) - 1]):
                    #print(item)
                    listFrom.remove(item)
                    listTo.append(item)
                    break
        print(listTo)


sul = SolutionOne()
for i in range(1,17):
    print(sul.grayCode(i))

